유전 프로그래밍
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
유전 프로그래밍(Genetic Programming, GP)은 앨런 튜링에 의해 처음 제안된 개념으로, 유전 알고리즘과 유사하게 컴퓨터 프로그램을 진화시키는 기술이다. GP는 일반적으로 트리 구조로 표현되는 컴퓨터 프로그램을 진화시키며, 트리 구조 외에도 선형, 스택, 그래프 모델 등 다양한 표현 방식을 사용한다. GP는 선택, 교차, 변이, 복제 등의 연산을 통해 프로그램을 발전시키며, 자동 프로그래밍, 기계 학습, 문제 해결 등 다양한 분야에 응용된다.
더 읽어볼만한 페이지
- 진화 연산 - 유전 알고리즘
유전 알고리즘은 생물 진화 과정을 모방하여 최적해를 탐색하는 계산 최적화 기법으로, 해를 유전자로 표현하고 적합도 함수를 통해 평가하며 선택, 교차, 돌연변이 연산을 반복하여 최적해에 근접하는 해를 생성하며, 성능은 매개변수에 영향을 받고 초기 수렴 문제 해결을 위한 다양한 변형 기법과 관련 기법이 존재한다. - 유전 알고리즘 - 양적 형질
양적 형질은 연속적인 표현형을 가지며 다양한 유전자와 환경적 요인의 영향을 받아 유전성을 띠고, 양적 유전학 연구를 통해 유전적 요인과 환경적 요인의 영향을 파악한다. - 진화 알고리즘 - 입자 군집 최적화
입자 군집 최적화는 입자들의 군집을 통해 최적해를 찾는 계산 지능 기반 알고리즘으로, 각 입자는 자신의 최적 위치와 군집 전체의 최적 위치를 활용해 속도와 위치를 업데이트하며 최적해를 탐색한다. - 진화 알고리즘 - 유전 알고리즘
유전 알고리즘은 생물 진화 과정을 모방하여 최적해를 탐색하는 계산 최적화 기법으로, 해를 유전자로 표현하고 적합도 함수를 통해 평가하며 선택, 교차, 돌연변이 연산을 반복하여 최적해에 근접하는 해를 생성하며, 성능은 매개변수에 영향을 받고 초기 수렴 문제 해결을 위한 다양한 변형 기법과 관련 기법이 존재한다.
유전 프로그래밍 | |
---|---|
개요 | |
분야 | 인공지능, 기계 학습, 진화 연산 |
패러다임 | 진화 알고리즘 |
영감 | 생물학적 진화 |
문제 유형 | 최적화 문제, 자동 프로그래밍 |
역사 | |
창시자 | 존 코자 |
개발 시기 | 1990년대 초 |
특징 | |
기반 | 유전 알고리즘 |
목표 | 컴퓨터 프로그램 자동 생성 |
표현 방식 | 트리 구조, 그래프 구조, 선형 구조 등 |
연산자 | 교차 연산, 돌연변이 연산, 선택 연산 |
응용 분야 | |
예시 | 로봇 제어 이미지 처리 데이터 마이닝 금융 모델링 게임 인공지능 |
장점 및 단점 | |
장점 | 사람의 직관에 의존하지 않고 새로운 해결책 발견 가능 복잡한 문제에 대한 자동화된 해결책 제공 |
단점 | 계산 비용이 높음 생성된 프로그램의 해석이 어려울 수 있음 |
관련 기술 | |
관련 기술 | 유전 알고리즘 진화 전략 진화 연산 기계 학습 인공 신경망 |
참고 자료 | |
서적 | Genetic Programming: On the Programming of Computers by Means of Natural Selection by John R. Koza (1992) Genetic Programming II: Automatic Discovery of Reusable Programs by John R. Koza (1994) Genetic Programming III: Darwinian Invention & Problem Solving by John R. Koza (1999) |
학술지 | Genetic Programming and Evolvable Machines |
2. 역사
앨런 튜링은 1950년에 유전 프로그래밍에 대한 최초의 제안을 한 것으로 보인다.[1] 1981년, 리처드 포사이스는 범죄 현장 증거 분류를 위해 트리로 표현된 소규모 프로그램을 성공적으로 진화시키는 것을 시연했다.[2]
유전 프로그래밍(GP)은 다양한 종류의 프로그램 표현 방식을 사용하며, 각각 고유한 특징과 장단점을 가진다.
1988년, 존 코자는 프로그램 진화를 위한 유전 알고리즘 발명을 특허냈다.[5] 1992년부터 시작된 코자의 4권짜리 책 시리즈[8]와 비디오[9]를 통해 유전 프로그래밍이 널리 알려지게 되었다. 1996년, 코자는 연례 유전 프로그래밍 컨퍼런스를 시작했고,[12] 1998년에는 연례 EuroGP 컨퍼런스[13]와 코자가 편집한 GP 시리즈의 첫 번째 책이 출판되었다.[14] 같은 해, 첫 번째 GP 교과서도 출판되었다.[15] 2010년, 코자[11]는 유전 프로그래밍이 인간과 경쟁할 수 있는 77가지 결과를 열거했다.
현재 유전 프로그래밍 관련 문헌은 10,000개 이상이며,[10] 전문 GP 저널[16]과 여러 권의 GP 책[15]이 출판되는 등 활발한 연구가 이루어지고 있다.
3. 종류 및 방법
대부분의 표현 방식에는 구조적으로 비효율적인 코드인 인트론이 존재한다. 인트론은 개체의 성능에 영향을 주지 않지만, 변이 연산 시 다른 자손을 생성할 확률을 변경하여 개체의 변이 특성을 바꾼다. 실험에 따르면, 비코딩 유전자를 허용하는 표현 방식을 사용하면 더 빠른 수렴을 보이는 경향이 있다.[39][40]
유전 프로그래밍의 탐색은 유전 알고리즘과 동일하게 진행되지만,[1] 유전자형 표현 방식의 차이로 인해 교차 및 돌연변이 방법은 약간 다르다.
엘리트주의는 현재 세대에서 가장 뛰어난 개체를 다음 세대로 넘기는 기술로, 성능 저하를 방지하기 위해 사용된다.
3. 1. 프로그램 표현
유전 프로그래밍(GP)은 다양한 프로그램 표현 방식을 사용한다. 존 코자가 제안한 리스프와 비슷한 트리 구조 외에도 선형 유전 프로그래밍, 유향 멀티그래프를 이용한 μGP, 3 주소 코드를 사용하는 다중 표현 프로그래밍, 데카르트 유전 프로그래밍 등이 있다.
대부분의 표현 방식에는 구조적으로 비효과적인 코드인 인트론이 존재한다. 이러한 비코딩 유전자는 개체의 성능에 영향을 미치지 않지만, 변이 연산 시 다른 자손을 생성할 확률을 변경하여 개체의 변이 특성을 바꾼다. 실험에 따르면, 비코딩 유전자를 허용하는 표현 방식을 사용하면 그렇지 않은 방식보다 더 빠른 수렴을 보이는 경향이 있다.[39][40]
3. 1. 1. 트리(tree) 모델
존 코자(John Koza)가 처음 제안한 방식으로, 리스프와 비슷한 트리 구조의 명령을 이용해 계산을 수행하는 것이 특징이다.[29] --
유전 프로그래밍(GP)은 컴퓨터 프로그램을 진화시키며, 전통적으로 메모리 내에서 트리 구조로 표현된다.[29] 트리는 재귀적인 방식으로 쉽게 평가할 수 있다. 모든 내부 노드는 연산자 함수를 가지며, 모든 터미널 노드는 피연산자를 가지므로, 수학적 표현식을 쉽게 진화시키고 평가할 수 있다. 따라서 전통적으로 GP는 트리 구조를 자연스럽게 구현하는 프로그래밍 언어 (예: Lisp)의 사용을 선호한다.
해 개체를 나타내는 트리에 어떤 함수 기호를 사용할지는 사전에 정해두는 것이 일반적이며, {+, −, ×, ÷} 등 일반적인 연산자 외에 {sin, cos, tan, exp, loge''x'', ''x''2}와 같은 단항의 초등 함수 등을 사용하기도 한다. 또한, 두 개의 가지가 가진 값의 최댓값이나 최솟값을 취하는 함수 max, min 외에, 무조건 한쪽 가지의 값만 사용하고 다른 한쪽은 무시하는 함수를 설정하기도 한다. 예를 들어,
3. 1. 2. 스택(stack) 모델
Forth와 비슷한 스택을 기반으로 하는 명령을 이용해 계산하며, 빠른 속도를 보장하는 것이 특징이다.[34][35][36]
3. 1. 3. 선형(linear) 모델
유전 프로그래밍(GP)은 컴퓨터 프로그램을 진화시키며, 전통적으로 메모리 내에서 트리 구조로 표현된다.[29] 트리가 아닌 다른 표현 방식도 제안되고 성공적으로 구현되었는데, 예를 들어 선형 유전 프로그래밍은 더 전통적인 명령형 프로그래밍 언어에 적합하다.[30][31] 상업용 GP 소프트웨어인 ''Discipulus''는 더 나은 성능을 달성하기 위해 바이너리 기계 코드("AIM")의 자동 유도[32]를 사용한다. ''μGP''[33]는 주어진 어셈블리 언어의 구문을 완전히 활용하는 프로그램을 생성하기 위해 유향 멀티그래프를 사용한다. 다중 표현 프로그래밍은 솔루션을 인코딩하기 위해 3 주소 코드를 사용한다.
3. 1. 4. 그래프(graph) 모델
이 문서에는 내용이 비어 있습니다. 내용을 추가해 주세요.
3. 2. 연산
유전 프로그래밍의 탐색 흐름은 유전 알고리즘과 완전히 동일하다.[1] 단, 유전자형의 표현 방법이 다르기 때문에 교차 및 돌연변이 방법이 약간 다른 형태로 되어 있다.
교차는 주로 부분 트리의 교환으로 이루어진다. 유전 프로그래밍에서 적합도가 높은 두 개체는 자식 하나 또는 두 개체를 생성하기 위해 부모로 선택된다. 트리 유전 프로그래밍에서 이러한 부모는 최상위 노드를 루트로 하는 역 Lisp 형식의 트리로 표현된다. 서브트리 교차(crossover)에서 각 부모는 무작위로 서브트리를 선택한다. 루트를 기증하는 부모에서 선택된 서브트리는 제거되고 다른 부모에서 무작위로 선택된 서브트리의 복사본으로 대체되어 새로운 자식 트리를 생성한다. 때로는 두 자식 교차가 사용되는데, 이 경우 제거된 서브트리는 삭제되는 것이 아니라 두 번째 부모의 복사본에 복사되어 (복사본에서) 무작위로 선택된 서브트리를 대체한다. 따라서 이러한 유형의 서브트리 교차는 적합도가 높은 두 개의 트리를 가져와 두 개의 자식 트리를 생성한다.
위 그림은 구체적인 교차의 예시를 보여준다. 함수 와 함수 가 되는 트리를 교차시켜 함수 와 함수 가 되는 트리가 생성되었음을 나타낸다. 교차를 수행할 부분 트리의 위치는 일반적으로 무작위로 결정한다.
변이에는 다양한 종류가 존재한다. 이러한 변이는 문법적으로 올바른 부모로부터 시작하여 문법적으로 올바른 자식을 무작위로 생성하는 것을 목표로 한다. 애니메이션에서는 하위 트리가 무작위로 선택되어 (노란색으로 강조 표시) 제거되고 무작위로 생성된 하위 트리로 대체된다.
다른 변이 연산자는 트리의 잎(외부 노드)을 선택하여 무작위로 선택된 잎으로 대체한다. 또 다른 변이는 함수(내부 노드)를 무작위로 선택하여 동일한 아리티(입력 수)를 가진 다른 함수로 대체하는 것이다. 호이스트 변이는 하위 트리를 무작위로 선택하여 자체 내부의 하위 트리로 대체한다. 따라서 호이스트 변이는 자식의 크기를 작게 만든다. 잎 및 동일 아리티 함수 대체는 자식이 부모와 동일한 크기를 갖도록 한다. 반면 하위 트리 변이(애니메이션에서)는 함수 및 단자 집합에 따라 트리 크기를 증가시키거나 감소시키는 경향을 가질 수 있다. 다른 하위 트리 기반 변이는 대체 하위 트리의 크기와 자식 트리의 크기를 신중하게 제어하려고 시도한다.
마찬가지로 선형 유전 프로그래밍 변이에도 여러 유형이 있으며, 각 유형은 변이된 자식이 여전히 문법적으로 올바른지 확인하려고 한다.
적합성 기준에 따라 선택된 일부 개체는 교차에 참여하지 않고 다음 세대로 복제되는데, 이는 자연계의 무성 생식과 유사하다.[1] 이들은 추가적인 돌연변이의 영향을 받을 수 있다.[1]
3. 2. 1. 선택 (Selection)
선택은 현재 세대에서 다음 세대의 부모 역할을 할 특정 개체를 선택하는 과정이다. 개체는 더 나은 성능을 보이는 개체가 선택될 확률이 더 높도록 확률적으로 선택된다.[18] 유전 프로그래밍에서 가장 일반적으로 사용되는 선택 방법은 토너먼트 선택이지만, 적합도 비례 선택, 렉시케이스 선택[41] 등 다른 방법이 많은 유전 프로그래밍 문제에 더 나은 성능을 보이는 것으로 나타났다.
엘리트주의는 현재 세대에서 가장 뛰어난 개체 (또는 가장 뛰어난 ''n''개의 개체)로 다음 세대를 시드하는 것으로, 성능 저하를 방지하기 위해 때때로 사용되는 기술이다.
3. 2. 2. 교차 (Crossover)
교차는 주로 부분 트리의 교환으로 이루어진다. 유전 프로그래밍에서 적합도가 높은 두 개체는 자식 하나 또는 두 개체를 생성하기 위해 부모로 선택된다. 트리 유전 프로그래밍에서 이러한 부모는 최상위 노드를 루트로 하는 역 Lisp 형식의 트리로 표현된다. 서브트리 교차(crossover)에서 각 부모는 무작위로 서브트리를 선택한다. 루트를 기증하는 부모에서 선택된 서브트리는 제거되고 다른 부모에서 무작위로 선택된 서브트리의 복사본으로 대체되어 새로운 자식 트리를 생성한다.
때로는 두 자식 교차가 사용되는데, 이 경우 제거된 서브트리는 삭제되는 것이 아니라 두 번째 부모의 복사본에 복사되어 (복사본에서) 무작위로 선택된 서브트리를 대체한다. 따라서 이러한 유형의 서브트리 교차는 적합도가 높은 두 개의 트리를 가져와 두 개의 자식 트리를 생성한다.
아래 그림은 구체적인 교차의 예시를 보여준다.
이 예에서는 함수 와 함수 가 되는 트리를 교차시켜 함수 와 함수 가 되는 트리가 생성되었음을 나타낸다. 교차를 수행할 부분 트리의 위치는 일반적으로 무작위로 결정한다.
3. 2. 3. 변이 (Mutation)
유전 프로그래밍에는 다양한 종류의 변이가 존재한다. 이러한 변이는 문법적으로 올바른 부모로부터 시작하여 문법적으로 올바른 자식을 무작위로 생성하는 것을 목표로 한다. 애니메이션에서는 하위 트리가 무작위로 선택되어 (노란색으로 강조 표시) 제거되고 무작위로 생성된 하위 트리로 대체된다.
다른 변이 연산자는 트리의 잎(외부 노드)을 선택하여 무작위로 선택된 잎으로 대체한다. 또 다른 변이는 함수(내부 노드)를 무작위로 선택하여 동일한 아리티(입력 수)를 가진 다른 함수로 대체하는 것이다. 호이스트 변이는 하위 트리를 무작위로 선택하여 자체 내부의 하위 트리로 대체한다. 따라서 호이스트 변이는 자식의 크기를 작게 만든다. 잎 및 동일 아리티 함수 대체는 자식이 부모와 동일한 크기를 갖도록 한다. 반면 하위 트리 변이(애니메이션에서)는 함수 및 단자 집합에 따라 트리 크기를 증가시키거나 감소시키는 경향을 가질 수 있다. 다른 하위 트리 기반 변이는 대체 하위 트리의 크기와 자식 트리의 크기를 신중하게 제어하려고 시도한다.
마찬가지로 선형 유전 프로그래밍 변이에도 여러 유형이 있으며, 각 유형은 변이된 자식이 여전히 문법적으로 올바른지 확인하려고 한다. 유전 프로그래밍의 탐색 흐름은 유전 알고리즘과 완전히 동일하다. 단, 유전자형의 표현 방법이 다르기 때문에 교차 및 돌연변이 방법이 약간 다른 형태로 되어 있다.
3. 2. 4. 복제 (Replication)
적합성 기준에 따라 선택된 일부 개체는 교차에 참여하지 않고 다음 세대로 복제되는데, 이는 자연계의 무성 생식과 유사하다.[1] 이들은 추가적인 돌연변이의 영향을 받을 수 있다.[1]
4. 응용 분야
유전 프로그래밍(GP)은 자동 프로그래밍 도구, 기계 학습 도구, 자동 문제 해결 엔진으로 성공적으로 사용되어 왔다.[18] 해결책의 정확한 형태를 미리 알 수 없거나 근사적인 해결책이 허용되는 분야에서 특히 유용하며, 곡선 맞춤, 데이터 모델링, 기호 회귀, 특징 선택, 분류 등에 응용된다. 존 R. 코자(John R. Koza)는 유전 프로그래밍이 인간과 경쟁할 수 있는 결과를 76가지 사례에서 만들어냈다고 언급했다.[42]
금융, 화학 산업, 바이오인포매틱스[26][27], 철강 산업 등 여러 분야에서 산업적으로 활용되고 있다.[28]
유전 프로그래밍은 함수 동정 문제, 신경망, 전자 회로 설계, 로봇 제어 프로그래밍 작성 등에 적용된다. 예를 들어 함수 동정 문제에서 해는 함수이기 때문에 배열로 표현하기 어렵지만, 아래 그림과 같은 트리 구조를 사용하면 수식을 쉽게 표현할 수 있다.
위 트리 구조는 를 나타낸다.
해를 나타내는 트리에 사용되는 함수 기호는 {+, −, ×, ÷} 등 일반적인 연산자, {sin, cos, tan, exp, loge''x'', ''x''2}와 같은 단항 초등 함수, 두 값의 최댓값/최솟값을 취하는 max, min, 한쪽 가지만 사용하는 함수 등 다양하며, 사전에 정의된다.
5. 관련 기법
참조
[1]
웹사이트
Computing Machinery and Intelligence
https://www.cs.bham.[...]
2018-05-19
[2]
웹사이트
BEAGLE A Darwinian Approach to Pattern Recognition
https://www.cs.bham.[...]
2018-05-19
[3]
문서
A personal communication with Tom Westerdale
http://www.dcs.bbk.a[...]
[4]
웹사이트
A representation for the Adaptive Generation of Simple Sequential Programs
https://www.cs.bham.[...]
2018-05-19
[5]
웹사이트
Non-Linear Genetic Algorithms for Solving Problems
https://www.cs.bham.[...]
2018-05-19
[6]
웹사이트
Hierarchical genetic algorithms operating on populations of computer programs
https://www.cs.bham.[...]
2018-05-19
[7]
간행물
Computer-aided gas pipeline operation using genetic algorithms and rule learning
University of Michigan at Ann Arbor, Michigan
1983
[8]
웹사이트
Genetic Programming: On the Programming of Computers by Means of Natural Selection
https://www.cs.bham.[...]
2018-05-19
[9]
웹사이트
Genetic Programming:The Movie
https://www.youtube.[...]
2021-05-20
[10]
웹사이트
The effects of recombination on phenotypic exploration and robustness in evolution
http://gpbib.cs.ucl.[...]
2021-05-20
[11]
웹사이트
Human-competitive results produced by genetic programming
https://www.cs.bham.[...]
2018-05-20
[12]
웹사이트
Genetic Programming 1996: Proceedings of the First Annual Conference
https://www.cs.bham.[...]
2018-05-19
[13]
웹사이트
Genetic Programming
https://www.cs.bham.[...]
2018-05-19
[14]
웹사이트
Genetic Programming and Data Structures: Genetic Programming + Data Structures = Automatic Programming!
https://www.cs.bham.[...]
2018-05-20
[15]
웹사이트
Genetic Programming -- An Introduction; On the Automatic Evolution of Computer Programs and its Applications
https://www.cs.bham.[...]
2018-05-20
[16]
논문
Editorial Introduction
2000-04-01
[17]
웹사이트
Genetic Programming Theory and Practice
https://www.cs.bham.[...]
2018-05-20
[18]
웹사이트
A Field Guide to Genetic Programming
http://www.gp-field-[...]
2018-05-20
[19]
웹사이트
Data Mining and Knowledge Discovery with Evolutionary Algorithms
https://www.cs.bham.[...]
2018-05-20
[20]
웹사이트
EDDIE beats the bookies
https://www.cs.bham.[...]
2018-05-20
[21]
웹사이트
Applying Computational Intelligence How to Create Value
https://www.cs.bham.[...]
2018-05-20
[22]
웹사이트
Human-competitive machine invention by means of genetic programming
https://www.cs.bham.[...]
2018-05-20
[23]
웹사이트
Discovery of Human-Competitive Image Texture Feature Extraction Programs Using Genetic Programming
https://www.cs.bham.[...]
2018-05-20
[24]
웹사이트
Three Ways to Grow Designs: A Comparison of Embryogenies for an Evolutionary Design Problem
https://www.cs.bham.[...]
2018-05-20
[25]
논문
Cellular encoding as a graph grammar - IET Conference Publication
https://ieeexplore.i[...]
1993-04
[26]
웹사이트
Genetic Algorithm Decoding for the Interpretation of Infra-red Spectra in Analytical Biotechnology
https://www.cs.bham.[...]
2018-05-20
[27]
웹사이트
Genetic Programming for Mining DNA Chip data from Cancer Patients
https://www.cs.bham.[...]
2018-05-20
[28]
웹사이트
Genetic Programming and Jominy Test Modeling
https://www.cs.bham.[...]
2018-05-20
[29]
문서
A Representation for the Adaptive Generation of Simple Sequential Programs
http://www.sover.net[...]
[30]
서적
Genetic Programming: An Introduction
Morgan Kaufmann
1999
[31]
문서
A Comparison of Cartesian Genetic Programming and Linear Genetic Programming
http://www.cs.mun.ca[...]
[32]
문서
(Peter Nordin, 1997, Banzhaf et al., 1998, Section 11.6.2-11.6.3)
[33]
웹사이트
μGP (MicroGP)
http://ugp3.sourcefo[...]
[34]
웹사이트
Stack-Based Genetic Programming
http://gpbib.cs.ucl.[...]
2021-05-20
[35]
논문
Genetic Programming and Autoconstructive Evolution with the Push Programming Language
2002-03-01
[36]
서적
Proceedings of the 7th annual conference on Genetic and evolutionary computation
ACM
2005-06-25
[37]
서적
Lecture Notes in Computer Science
Springer Berlin Heidelberg
1998
[38]
간행물
Grammatical evolution
2001
[39]
웹사이트
Cartesian Genetic Programming
https://www.springer[...]
2015-09-24
[40]
문서
A New Crossover Technique for Cartesian Genetic Programming
http://www.cs.bham.a[...]
2007
[41]
서적
Proceedings of the 14th annual conference companion on Genetic and evolutionary computation
https://dl.acm.org/c[...]
ACM
[42]
간행물
Human-competitive results produced by genetic programming
[43]
웹사이트
Humies =Human-Competitive Awards
http://www.human-com[...]
[44]
웹사이트
1987 THESIS ON LEARNING HOW TO LEARN, METALEARNING, META GENETIC PROGRAMMING, CREDIT-CONSERVING MACHINE LEARNING ECONOMY
http://www.idsia.ch/[...]
[45]
서적
GECCO '16 Companion : proceedings of the 2016 Genetic and Evolutionary Computation Conference : July 20-24, 2016, Denver, Colorado, USA
2016-07-20
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com